/*
 * Copyright (C), 2015-2018
 * FileName: Solution112
 * Author:   zhao
 * Date:     2018/9/9 20:04
 * Description: 112. 路径总和
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.diynode.TreeNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈112. 路径总和〉
 *
 * @author zhao
 * @date 2018/9/9 20:04
 * @since 1.0.1
 */
public class Solution112 {
  /**************************************
   * 题目
   给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

   说明: 叶子节点是指没有子节点的节点。

   示例:
   给定如下二叉树，以及目标和 sum = 22，

   5
   / \
   4   8
   /   / \
   11  13  4
   /  \      \
   7    2      1
   返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
   **************************************/

  /**************************************
   *
   * 想法：
   *    使用之前104的递归
   *    调用时候添加一个参数，之前的和
   * 我的做法
   *    超过65%的测试案例
   * 总结：
   *     如果后面是null就不进行递归了
   * ***********************************/
  public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
      return false;
    }

    return recDepth(root, 0, sum);
  }

  private boolean recDepth(TreeNode root, int lastValue, int target) {
    int nowValue = lastValue + root.val;
    if (root.left == null && root.right == null) {
      return nowValue == target;
    }
    if (root.left == null) {
      return recDepth(root.right, nowValue, target);
    }
    if (root.right == null) {
      return recDepth(root.left, nowValue, target);
    }

    return recDepth(root.left, nowValue, target) || recDepth(root.right, nowValue, target);
  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public boolean better(TreeNode root, int sum) {

    if (root == null) {
      return false;
    }

    if (root.left == null && root.right == null) {
      return sum == root.val;
    }

    if (root.left == null) {
      return better(root.right, sum - root.val);
    }

    if (root.right == null) {
      return better(root.left, sum - root.val);
    }

    return better(root.left, sum - root.val) || better(root.right, sum - root.val);

  }

}
